package _binary_tree

import common.TreeNode

/**
 * https://leetcode.cn/problems/maximum-difference-between-node-and-ancestor/description
 *
 * ```
 * 1026. 节点与其祖先之间的最大差值
 * 给定二叉树的根节点 root，找出存在于 不同 节点 A 和 B 之间的最大值 V，其中 V = |A.val - B.val|，且 A 是 B 的祖先。
 * （如果 A 的任何子节点之一为 B，或者 A 的任何子节点是 B 的祖先，那么我们认为 A 是 B 的祖先）
 *
 * 示例 1：
 * 输入：root = [8,3,10,1,6,null,14,null,null,4,7,13]
 * 输出：7
 * 解释：
 * 我们有大量的节点与其祖先的差值，其中一些如下：
 * |8 - 3| = 5
 * |3 - 7| = 4
 * |8 - 1| = 7
 * |10 - 13| = 3
 * 在所有可能的差值中，最大值 7 由 |8 - 1| = 7 得出。
 *
 * 示例 2：
 * 输入：root = [1,null,2,null,0,3]
 * 输出：3
 *
 *
 * 提示：
 * 树中的节点数在 2 到 5000 之间。
 * 0 <= Node.val <= 105
 * ```
 */
class leetcode_1026 {
    private fun maxAncestorDiff(root: TreeNode?): Int {
        /**
        题型： 二叉树的前序遍历

        思路：
        遍历时，记录一条路径的最大值和最小值，二值之差就是这条路径上的最大差值。

        空间复杂度： O(N)

        时间复杂度： O(N)
         */
        if (null == root) {
            return 0
        }
        find(root, Int.MIN_VALUE, Int.MAX_VALUE)
        return result
    }

    var result: Int = 0

    private fun find(root: TreeNode?, max: Int, min: Int) {
        // 1 确定函数参数以及返回值
        // 2 确定终止调价
        if (null == root) {
            return
        }

        // 3 确定单层递归的处理逻辑 : 前序遍历
        // 中
        val newMax: Int = Math.max(max, root.`val`)
        val newMin: Int = Math.min(min, root.`val`)
        // 左
        find(root.left, newMax, newMin)
        // 右
        find(root.right, newMax, newMin)

        // 记录最大差值
        result = Math.max(result, newMax - newMin)
    }

    fun maxAncestorDiff2(root: TreeNode?): Int {
        return collect(root, Int.MIN_VALUE, Int.MAX_VALUE)
    }

    fun collect(root: TreeNode?, max: Int, min: Int): Int {
        // 1 确定函数参数以及返回值
        // 2 确定终止条件
        if (null == root) {
            return 0
        }
        // 3 确定单层递归的终止条件：前序遍历
        // 中
        val newMax = Math.max(root.`val`, max)
        val newMin = Math.min(root.`val`, min)

        // 左
        val left = collect(root.left, newMax, newMin)

        // 右
        val right = collect(root.right, newMax, newMin)

        return Math.max(Math.max(newMax - newMin, left), right)
    }
}